#ifndef AVLTREEWINDOW_H
#define AVLTREEWINDOW_H

#include <QMainWindow>
#include <QVBoxLayout>
#include <QHBoxLayout>
#include <QTextEdit>
#include <QLineEdit>
#include <QPushButton>
#include <QLabel>
#include <QGroupBox>
#include <QMessageBox>
#include <QComboBox>
#include <QWidget>
#include <QPainter>
#include <QScrollArea>
#include <QScrollBar>
#include <QTimer>
#include <QSet>
#include <cmath>

// AVL树节点结构
struct AVLNode {
    int data;
    int height;
    AVLNode* left;
    AVLNode* right;
    AVLNode(int val) : data(val), height(1), left(nullptr), right(nullptr) {}
};

// 自定义队列
class AVLNodeQueue {
private:
    struct QueueNode {
        AVLNode* data;
        QueueNode* next;
        QueueNode(AVLNode* val) : data(val), next(nullptr) {}
    };

    QueueNode* m_front;
    QueueNode* m_rear;
    int m_size;

public:
    AVLNodeQueue() : m_front(nullptr), m_rear(nullptr), m_size(0) {}

    ~AVLNodeQueue() {
        while (!empty()) {
            pop();
        }
    }

    void push(AVLNode* value) {
        QueueNode* newNode = new QueueNode(value);
        if (m_rear == nullptr) {
            m_front = m_rear = newNode;
        } else {
            m_rear->next = newNode;
            m_rear = newNode;
        }
        m_size++;
    }

    void pop() {
        if (empty()) return;
        QueueNode* temp = m_front;
        m_front = m_front->next;
        if (m_front == nullptr) {
            m_rear = nullptr;
        }
        delete temp;
        m_size--;
    }

    AVLNode* front() const {
        return empty() ? nullptr : m_front->data;
    }

    bool empty() const {
        return m_front == nullptr;
    }

    int size() const {
        return m_size;
    }
};

class AVLTreeVisualizationWidget : public QWidget
{
    Q_OBJECT

public:
    explicit AVLTreeVisualizationWidget(QWidget *parent = nullptr);
    ~AVLTreeVisualizationWidget();

    void setRoot(AVLNode* rootNode);
    QSize getTreeSize() const { return QSize(m_treeWidth, m_treeHeight); }

    // 遍历可视化
    void startTraversal(const QVector<AVLNode*>& order);
    void nextTraversalStep();
    void resetTraversal();
    bool isTraversing() const { return m_currentTraverseIndex >= 0 && m_currentTraverseIndex < m_traverseOrder.size(); }

    // 旋转动画
    void startRotationAnimation(AVLNode* pivotNode, const QString& rotationType);
    void nextRotationStep();
    bool isRotating() const { return m_rotationSteps.size() > 0; }

    QPoint getCurrentTraverseNodePosition() const;

    // 添加获取平衡因子的公共方法
    int getNodeBalance(AVLNode* node) const;

signals:
    void traversalStepCompleted(const QString& currentResult);
    void rotationStepCompleted(const QString& stepInfo);

protected:
    void paintEvent(QPaintEvent* event) override;

private:
    void calculateTreeDimensions();
    void calculateNodePositions();
    void drawTree(QPainter& painter);
    void drawAVLNode(QPainter& painter, AVLNode* node, int x, int y);
    void drawPointerLine(QPainter& painter, int startX, int startY, int endX, int endY, const QColor& color = Qt::blue);
    void drawNullPointer(QPainter& painter, int startX, int startY, bool isLeft);

    int getTreeHeight(AVLNode* node);
    int getTreeWidth(AVLNode* node);
    void calculateSubtreeWidth(AVLNode* node, int level, int& maxWidth);

    AVLNode* root;
    int m_treeWidth;
    int m_treeHeight;

    // 节点位置信息
    QVector<int> m_nodePositionsX;
    QVector<int> m_nodePositionsY;
    QVector<AVLNode*> m_nodePointers;

    // 遍历可视化
    AVLNode* m_currentTraverseNode;
    QVector<AVLNode*> m_traverseOrder;
    int m_currentTraverseIndex;

    // 旋转动画
    QVector<QString> m_rotationSteps;
    AVLNode* m_rotationPivotNode;
    QString m_currentRotationType;
    int m_currentRotationStep;
};

class AVLTreeWindow : public QMainWindow
{
    Q_OBJECT

public:
    AVLTreeWindow(QWidget *parent = nullptr);
    ~AVLTreeWindow();

signals:
    void returnToMainMenu();

private slots:
    void onInsert();
    void onDelete();
    void onSearch();
    void onTraverse();
    void onClear();
    void onGenerateRandom();
    void onReturnToMainMenu();
    void onTraversalStepCompleted(const QString& currentResult);
    void onRotationStepCompleted(const QString& stepInfo);

private:
    void setupUI();
    void updateDisplay();
    void clearTree(AVLNode* node);

    // AVL树核心操作
    int getHeight(AVLNode* node);
    int getBalance(AVLNode* node);
    AVLNode* rotateRight(AVLNode* y);
    AVLNode* rotateLeft(AVLNode* x);
    AVLNode* insert(AVLNode* node, int value);
    AVLNode* deleteNode(AVLNode* node, int value);
    bool search(AVLNode* node, int value);
    AVLNode* minValueNode(AVLNode* node);

    // 遍历方法
    void preorderTraversal(AVLNode* node, QVector<AVLNode*>& result);
    void inorderTraversal(AVLNode* node, QVector<AVLNode*>& result);
    void postorderTraversal(AVLNode* node, QVector<AVLNode*>& result);
    void levelOrderTraversal(AVLNode* node, QVector<AVLNode*>& result);

    // 工具函数
    int max(int a, int b) { return a > b ? a : b; }
    int randomInt(int min, int max);
    void scrollToNodePosition(const QPoint& nodePos);
    void performRotationWithAnimation(AVLNode* pivotNode, const QString& rotationType);

    AVLNode* m_root;
    int m_size;

    QTextEdit *m_display;
    QComboBox *m_traverseCombo;
    QLineEdit *m_insertEdit;
    QLineEdit *m_deleteEdit;
    QLineEdit *m_searchEdit;

    AVLTreeVisualizationWidget *m_visualizationWidget;
    QScrollArea *m_scrollArea;

    // 遍历和动画定时器
    QTimer *m_traverseTimer;
    QTimer *m_rotationTimer;
    QString m_currentTraverseResult;
    bool m_isTraversing;
    bool m_isRotating;
    int m_traverseSpeed;
};

static double my_atan2(double y, double x) { return atan2(y, x); }
static double my_cos(double x) { return cos(x); }
static double my_sin(double x) { return sin(x); }

#endif // AVLTREEWINDOW_H
